home *** CD-ROM | disk | FTP | other *** search
/ Amiga Tools 3 / Amiga Tools 3.iso / grafik / raytracing / rayshade-4.0.6.3 / libray / libobj / poly.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-09  |  8.1 KB  |  350 lines
  1. /*
  2.  * poly.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * poly.c,v 4.1 1994/08/09 07:59:50 explorer Exp
  17.  *
  18.  * poly.c,v
  19.  * Revision 4.1  1994/08/09  07:59:50  explorer
  20.  * Bump version to 4.1
  21.  *
  22.  * Revision 1.1.1.1  1994/08/08  04:52:10  explorer
  23.  * Initial import.  This is a prerelease of 4.0.6enh3, or 4.1 possibly.
  24.  *
  25.  * Revision 4.0.1.1  91/11/26  21:25:34  cek
  26.  * patch3: Additional check for degenerate polygon.
  27.  * 
  28.  * Revision 4.0  91/07/17  14:39:00  kolb
  29.  * Initial version.
  30.  * 
  31.  */
  32. #include "geom.h"
  33. #include "poly.h"
  34.  
  35. static Methods *iPolygonMethods = NULL;
  36. static char polyName[] = "polygon";
  37.  
  38. unsigned long PolyTests, PolyHits;
  39.  
  40. /*
  41.  * Create a reference to a polygon with vertices equal to those
  42.  * on the linked-list "plist."
  43.  */
  44. Polygon *
  45. PolygonCreate(plist, npoints, flipflag)
  46. PointList *plist;
  47. int npoints, flipflag;
  48. {
  49.     Polygon *poly;
  50.     Float indexval;
  51.     Vector *prev, *cur, anorm;
  52.     PointList *curp, *pltmp;
  53.     int i;
  54.  
  55.     if (npoints < 3) {
  56.         RLerror(RL_WARN, "Degenerate polygon.\n");
  57.         return (Polygon *)NULL;
  58.     }
  59.     
  60.     poly = (Polygon *)share_malloc(sizeof(Polygon));
  61.     /*
  62.      * Allocate space for the vertices.
  63.      */
  64.     poly->points = (Vector *)Malloc((unsigned)(npoints*sizeof(Vector)));
  65.     poly->npoints = npoints;
  66.  
  67.     /*
  68.      * Copy the vertices from the linked list to the array, freeing
  69.      * the linked list as we go so that the caller doesn't have
  70.      * to worry about doing so.
  71.      */
  72.     i = npoints -1;
  73.     for(curp = plist; curp != (PointList *)0; curp = pltmp) {
  74.         poly->points[i--] = curp->vec;
  75.         pltmp = curp->next;
  76.         free((voidstar)curp);
  77.     }
  78.  
  79.     /*
  80.      * Find normal to polygon.
  81.      */
  82.     poly->norm.x = poly->norm.y = poly->norm.z = 0.;
  83.     prev = &poly->points[poly->npoints -1];
  84.     for(i = 0,cur = poly->points;i < poly->npoints;i++, prev = cur, cur++) {
  85.         poly->norm.x += (prev->y - cur->y) * (prev->z + cur->z);
  86.         poly->norm.y += (prev->z - cur->z) * (prev->x + cur->x);
  87.         poly->norm.z += (prev->x - cur->x) * (prev->y + cur->y);
  88.     }
  89.  
  90.     if (VecNormalize(&poly->norm) == 0.) {
  91.         /*
  92.          * Degenerate normal --> degenerate polygon
  93.          */
  94.         RLerror(RL_WARN, "Degenerate polygon.\n");
  95.         free((voidstar)poly->points);
  96.         return (Polygon *)NULL;
  97.     }
  98.  
  99.     /*
  100.      * If filflag is true, flip the normal.
  101.      */
  102.     if (flipflag)
  103.         VecScale(-1, poly->norm, &poly->norm);
  104.  
  105.     /*
  106.      * Compute and store the plane constant.
  107.      */
  108.     poly->d = dotp(&poly->norm, &poly->points[0]);
  109.  
  110.     /*
  111.      * Find the "dominant" part of the normal vector.  This
  112.      * is used to turn the point-in-polygon test into a 2D problem.
  113.      */
  114.     anorm.x = fabs(poly->norm.x);
  115.     anorm.y = fabs(poly->norm.y);
  116.     anorm.z = fabs(poly->norm.z);
  117.     indexval = max(anorm.y, anorm.z);
  118.     indexval = max(anorm.x, indexval);
  119.  
  120.     if (indexval == anorm.x)
  121.         poly->index = XNORMAL;
  122.     else if (indexval == anorm.y)
  123.         poly->index = YNORMAL;
  124.     else
  125.         poly->index = ZNORMAL;
  126.  
  127.     return poly;
  128. }
  129.  
  130. Methods *
  131. PolygonMethods()
  132. {
  133.     if (iPolygonMethods == (Methods *)NULL) {
  134.         iPolygonMethods = MethodsCreate();
  135.         iPolygonMethods->create = (GeomCreateFunc *)PolygonCreate;
  136.         iPolygonMethods->methods = PolygonMethods;
  137.         iPolygonMethods->name = PolygonName;
  138.         iPolygonMethods->intersect = PolygonIntersect;
  139.         iPolygonMethods->normal = PolygonNormal;
  140.         iPolygonMethods->uv = PolygonUV;
  141.         iPolygonMethods->bounds = PolygonBounds;
  142.         iPolygonMethods->stats = PolygonStats;
  143.         iPolygonMethods->checkbounds = TRUE;
  144.         iPolygonMethods->closed = FALSE;
  145.     }
  146.     return iPolygonMethods;
  147. }
  148.  
  149. /*
  150.  * Quadrants are defined as:
  151.  *        |
  152.  *   1    |   0
  153.  *        |
  154.  * -------c--------
  155.  *        |
  156.  *   2    |   3
  157.  *        |
  158.  */
  159. #define quadrant(p, c) ((p.u<c.u) ? ((p.v<c.v) ? 2 : 1) : ((p.v<c.v) ? 3 : 0))
  160.  
  161. /*
  162.  * Perform ray-polygon intersection test.
  163.  */
  164. int
  165. PolygonIntersect(poly, ray, mindist, maxdist)
  166. Polygon *poly;
  167. Ray *ray;
  168. Float mindist, *maxdist;
  169. {
  170.     register int winding, i;
  171.     Vector dir, pos;
  172.     int quad, lastquad;
  173.     Float dist, left, right;
  174.     Vec2d center, cur, last;
  175.  
  176.     PolyTests++;
  177.     pos = ray->pos;
  178.     dir = ray->dir;
  179.     /*
  180.      * First, find where ray hits polygon plane, projecting
  181.      * along the polygon's dominant normal component.
  182.      */
  183.  
  184.     dist = dotp(&poly->norm, &dir);
  185.     if(fabs(dist) < EPSILON)
  186.         /*
  187.           * No intersection with polygon plane.
  188.          */
  189.         return FALSE;
  190.  
  191.     dist = (poly->d - dotp(&poly->norm, &pos)) / dist;
  192.     if(dist < mindist || dist > *maxdist)
  193.         /*
  194.          * Intersection point behind origin or too far.
  195.          */
  196.         return FALSE;
  197.  
  198.     /*
  199.      * Compute the point of intersection, projected appropriately.
  200.      */
  201.     if(poly->index == XNORMAL) {
  202.         center.u = pos.y + dist * dir.y;
  203.         center.v = pos.z + dist * dir.z;
  204.     } else if(poly->index == YNORMAL) {
  205.         center.v = pos.z + dist * dir.z;
  206.         center.u = pos.x + dist * dir.x;
  207.     } else  {
  208.         center.u = pos.x + dist * dir.x;
  209.         center.v = pos.y + dist * dir.y;
  210.     }    
  211.  
  212.     /*
  213.      * Is the point inside the polygon?
  214.      *
  215.      * Compute the winding number by finding the quadrant each
  216.      * polygon point lies in with respect to the the point in
  217.      * question, and computing a "delta" (winding number).  If we
  218.      * end up going around in a complete circle around
  219.      * the point (winding number is non-zero at the end), then
  220.      * we're inside.  Otherwise, the point is outside.
  221.      *
  222.      * Note that we can turn this into a 2D problem by projecting
  223.      * all the points along the axis defined by poly->index,
  224.      * the "dominant" part of the polygon's normal vector.
  225.      */
  226.     winding = 0;
  227.     VecProject(last, poly->points[poly->npoints -1], poly->index);
  228.     lastquad = quadrant(last, center);
  229.     for(i = 0; i < poly->npoints; i++, last = cur) {
  230.         VecProject(cur, poly->points[i], poly->index);
  231.         quad = quadrant(cur, center);
  232.         if (quad == lastquad)
  233.             continue;
  234.         if(((lastquad + 1) & 3) == quad)
  235.             winding++;
  236.         else if(((quad + 1) & 3) == lastquad)
  237.             winding--;
  238.         else {
  239.             /*
  240.              * Find where edge crosses
  241.              * center's X axis.
  242.              */
  243.             right = last.u - cur.u;
  244.             left = (last.v - cur.v) * (center.u - last.u);
  245.             if(left + last.v * right > right * center.v)
  246.                 winding += 2;
  247.             else
  248.                 winding -= 2;
  249.         }
  250.         lastquad = quad;
  251.     }
  252.  
  253.     if (winding != 0) {
  254.         *maxdist = dist;
  255.         PolyHits++;
  256.         return TRUE;
  257.     }
  258.     return FALSE;
  259. }
  260.  
  261. /*
  262.  * Return the normal to the polygon surface.
  263.  */
  264. /*ARGSUSED*/
  265. int
  266. PolygonNormal(poly, pos, nrm, gnrm)
  267. Polygon *poly;
  268. Vector *pos, *nrm, *gnrm;
  269. {
  270.     *gnrm = *nrm = poly->norm;
  271.     return FALSE;
  272. }
  273.  
  274. /*ARGSUSED*/
  275. void
  276. PolygonUV(poly, pos, norm, uv, dpdu, dpdv)
  277. Polygon *poly;
  278. Vector *pos, *norm, *dpdu, *dpdv;
  279. Vec2d *uv;
  280. {
  281.     /*
  282.      * Since there's no nice way to do this, we wimp out and
  283.      * do the following...
  284.      *
  285.      * Of course, we could force the user to specify U and V
  286.      * axes, but forcing them to use X and Y as U and V is
  287.      * just as arbitrary and much simpler to deal with.
  288.      */
  289.     uv->u = pos->x;
  290.     uv->v = pos->y;
  291.     if (dpdu) {
  292.         dpdu->x = 1.;
  293.         dpdu->y = dpdu->z = 0.;
  294.         dpdv->x = dpdv->z = 0.;
  295.         dpdv->y = 1.;
  296.     }
  297. }
  298.  
  299. /*
  300.  * Compute the extent of a polygon
  301.  */
  302. void
  303. PolygonBounds(poly, bounds)
  304. Polygon *poly;
  305. Float bounds[2][3];
  306. {
  307.     register int i;
  308.  
  309.     bounds[LOW][X] = bounds[HIGH][X] = poly->points[0].x;
  310.     bounds[LOW][Y] = bounds[HIGH][Y] = poly->points[0].y;
  311.     bounds[LOW][Z] = bounds[HIGH][Z] = poly->points[0].z;
  312.  
  313.     for (i = 1 ;i < poly->npoints; i++) {
  314.         if (poly->points[i].x < bounds[LOW][X])
  315.             bounds[LOW][X] = poly->points[i].x;
  316.         if (poly->points[i].x > bounds[HIGH][X])
  317.             bounds[HIGH][X] = poly->points[i].x;
  318.         if (poly->points[i].y < bounds[LOW][Y])
  319.             bounds[LOW][Y] = poly->points[i].y;
  320.         if (poly->points[i].y > bounds[HIGH][Y])
  321.             bounds[HIGH][Y] = poly->points[i].y;
  322.         if (poly->points[i].z < bounds[LOW][Z])
  323.             bounds[LOW][Z] = poly->points[i].z;
  324.         if (poly->points[i].z > bounds[HIGH][Z])
  325.             bounds[HIGH][Z] = poly->points[i].z;
  326.     }
  327. }
  328.  
  329. char *
  330. PolygonName()
  331. {
  332.     return polyName;
  333. }
  334.  
  335. void
  336. PolygonStats(tests, hits)
  337. unsigned long *tests, *hits;
  338. {
  339.     *tests = PolyTests;
  340.     *hits = PolyHits;
  341. }
  342.  
  343. void
  344. PolygonMethodRegister(meth)
  345. UserMethodType meth;
  346. {
  347.     if (iPolygonMethods)
  348.         iPolygonMethods->user = meth;
  349. }
  350.